#include "llvm/Pass.h"
#include "llvm/Module.h"
#include "llvm/Function.h"
#include "llvm/Instruction.h"
#include "llvm/Instructions.h"
#include "llvm/Constant.h"
#include "llvm/User.h"
#include "llvm/Use.h"
#include "llvm/Value.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/IRBuilder.h"
#include "llvm/Support/CFG.h"
#include "llvm/ExecutionEngine/ExecutionEngine.h"
#include "llvm/LLVMContext.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Support/CFG.h"
#include <vector>
#include <map>
#include <list>
#include <string>


using namespace llvm;

namespace {

  struct eSSAPass2 : public ModulePass
  {
    static char ID;
    eSSAPass2() : ModulePass(ID) {
    }

    void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
      AU.addRequired<DominatorTree>();
      AU.addRequired<PostDominatorTree>();
      AU.addRequired<DominanceFrontier>();
    }


    std::map <Instruction *, std::list <Instruction *> > lookup_for_other_branch;

    bool replace(Value *replacedInst, Instruction *replacingInst, DominatorTree &DT, DominanceFrontier &DF, bool CreatePHI, std::pair<BasicBlock*, BasicBlock*> sibling_blocks);
    void fillinjoinphi(Instruction *other_branch_inst, Instruction *replacingInst, DominatorTree &DT, DominanceFrontier &DF, std::pair<BasicBlock*, BasicBlock*> sibling_blocks);

 // bool isInDomFrontier(DominanceFrontier &DF, BasicBlock* curr_block, BasicBlock* sibling_block);

  
  bool isInDomFrontier(DominatorTree &DT, BasicBlock* curr_block, BasicBlock* sibling_block);

    virtual bool runOnModule(Module &M) 
    {
      /* Access each function through the function iterator of the moduke */
      for (Module::iterator func_iter = M.begin(), func_iter_end = M.end(); func_iter != func_iter_end; ++func_iter) 
      {
        Function &F = *func_iter;

        if (!F.isDeclaration())
        {
          lookup_for_other_branch.clear();
          DominatorTree &DT = getAnalysis<DominatorTree>(F);
          DominanceFrontier &DF = getAnalysis<DominanceFrontier>(F);
          for (inst_iterator i = inst_begin(F), E = inst_end(F); i != E; ++i)
          {
            Instruction *inst = &*i;
            if(isa<ICmpInst>(inst)) 
            {
              CmpInst::Predicate inequalityCond = ((ICmpInst*)inst)->getSignedPredicate();
              if((inequalityCond == CmpInst::ICMP_SLT) || (inequalityCond == CmpInst::ICMP_SLE))
              {
                Value *operands[2];       
                User::op_iterator opIt = inst->op_begin();
                Value *toBeReplaced;
                toBeReplaced = opIt->get();
                operands[0] = toBeReplaced;
                opIt++;
                toBeReplaced=opIt->get();
                operands[1] = toBeReplaced;

                bool Create_PHI = true;

                // if(isa<ConstantInt>(operands[0]) || isa<ConstantInt>(operands[1]))
                //                                          Create_PHI = false;

                BasicBlock *bbParent=inst->getParent();
                //errs() << *bbParent << "\n";
                std::list<BasicBlock *> b_list;
                bool phi_created = false;
                std::map<Value*, Value*> sibling_map;
                std::pair<BasicBlock*, BasicBlock*> sibling_blocks;
                TerminatorInst *term = bbParent->getTerminator();
                sibling_blocks.first = term->getSuccessor(0);
                sibling_blocks.second = term->getSuccessor(1);
                for(succ_iterator SI=succ_begin(bbParent), SE=succ_end(bbParent);SI!=SE;SI++)
                {
                  BasicBlock *piTarget = *SI;
                  for(BasicBlock::iterator b_it = piTarget->begin(); b_it != piTarget->end(); b_it++)
                  {
                    Instruction *replacingInst = &*b_it;
                    if(replacingInst->getOpcode() == Instruction::PHI)
                    {
                      PHINode *pinst = (PHINode *) replacingInst;
                      if(pinst->getNumIncomingValues() == 1)
                      {
                        //errs() << "looking at the PHI instruction " << *pinst << "\n";
                        Value* replacedInst = pinst->getIncomingValue(0);
                        std::map<Value*, Value* >::iterator it = sibling_map.find(replacedInst);
                        if (it != sibling_map.end())
                        {
                          Instruction* sibling_inst = (Instruction *)((*it).second);
                          fillinjoinphi(sibling_inst, replacingInst, DT, DF, sibling_blocks);
                        }

                        if (isa<ConstantInt>(replacedInst))
                          assert(0);
                        //continue;
                       if(!isa<ConstantInt>(replacedInst))
                        {
                          phi_created = replace(replacedInst, replacingInst, DT, DF, Create_PHI, sibling_blocks);
                          std::pair<Value*, Value*> sm_entry;
                          sm_entry.first = replacedInst;
                          sm_entry.second = replacingInst;
                          sibling_map.insert(sibling_map.begin(), sm_entry);
                        }
                      }
                    } 
                  } 
                }
              }
            }
          }
        }
      }
      return true;
    }
  };

  static void printInst(Instruction* inst)
  {
   //errs() << *inst << "\n";
  }

  static void printBB(BasicBlock* BB)
  {
    //errs() << *BB << "\n";
  }

 /* bool eSSAPass2::isInDomFrontier(DominanceFrontier &DF, BasicBlock* curr_block, BasicBlock* sibling_block)
  {
    DominanceFrontier::iterator it =  DF.find(sibling_block);

    for (;it != DF.end(); it++)
    {
      if ((*it).second.find(curr_block) != (*it).second.end())
        return true;
    }

    return false;
  }*/

  bool eSSAPass2::isInDomFrontier(DominatorTree &DT, BasicBlock* curr_block, BasicBlock* sibling_block)
  {
    
      if(!DT.properlyDominates(sibling_block, curr_block))  
      {
        // errs() << "properly dominates\n";

        bool dominates_parent = false;


        // errs() << "replaced inst is " << *replacedInst << "\n";

        // errs() << "user insr is " << *user_inst << "\n";
        // errs() << "user_block is " << *user_block << "\n";


        for (pred_iterator PI = pred_begin(curr_block), E = pred_end(curr_block); PI != E; ++PI) 
        {

          // errs() << "in for loop\n";

          BasicBlock *Pred = *PI;
          if(DT.dominates(sibling_block, Pred))
            dominates_parent = true;
        } 

        if(dominates_parent)
        {
          /* is a dominance frontier */
          return true;
        }
       }
   return false;
  }


  bool eSSAPass2::replace(Value *replacedInst, Instruction *replacingInst, DominatorTree &DT, DominanceFrontier &DF, bool CreatePHI, std::pair<BasicBlock*, BasicBlock*> sibling_blocks)
  {

    bool phi_created = false;;
    // errs() << "here\n";
    //errs() << *replacedInst << "\n";
    std::list <Instruction *> u_list;
    BasicBlock *bbParent=replacingInst->getParent()->getUniquePredecessor();
    if (bbParent == NULL && CreatePHI == true)
      return phi_created;
    for(Value::use_iterator u_it_l = replacedInst->use_begin(); u_it_l != replacedInst->use_end(); u_it_l++)
    {

      Instruction * user_inst = (Instruction *)((u_it_l.getUse()).getUser());

      //if ()
      //errs() << *user_inst << "\n";
      u_list.push_back(user_inst);
    }

    //errs() << "size of user list " << u_list.size() << "\n";
    for (std::list <Instruction *>::iterator inst_it = u_list.begin(); inst_it != u_list.end(); inst_it++)
    {
      // errs() << "here1\n";
      Instruction * user_inst = *inst_it;
      //errs() << *user_inst << "\n";
      BasicBlock *user_block = user_inst->getParent();
      BasicBlock *defining_block = replacingInst->getParent();
      // errs() << "user block was " << *user_block << "\n";
      // errs() << "defining block was " << *defining_block << "\n";
      if(DT.dominates(defining_block, user_block))
      {

        //errs() << "dominates was true\n";
        if(user_inst != replacingInst)
          user_inst->replaceUsesOfWith(replacedInst, replacingInst);//.set(replacingInst);  
      } 
      else if(!DT.properlyDominates(defining_block, user_block))  
      {
        // errs() << "properly dominates\n";

        bool dominates_parent = false;
        std::vector <BasicBlock *> dominated_parents;


        // errs() << "replaced inst is " << *replacedInst << "\n";

        // errs() << "user insr is " << *user_inst << "\n";
        // errs() << "user_block is " << *user_block << "\n";


        for (pred_iterator PI = pred_begin(user_block), E = pred_end(user_block); PI != E; ++PI) 
        {

          // errs() << "in for loop\n";

          BasicBlock *Pred = *PI;
          if(DT.dominates(defining_block, Pred))
          {
            dominates_parent = true;
            dominated_parents.push_back(Pred);
          }

        } 

        if(dominates_parent)
        {
          /* is a dominance frontier */

          BasicBlock* sibBlock = sibling_blocks.first;
          if (bbParent == sibBlock)
            sibBlock = sibling_blocks.second;

          if (isInDomFrontier(DT, user_block, sibBlock))
          {
            //errs() << "dominance frontier matched " << *(sibBlock) << " and " << *(bbParent) << "\n";
            //errs() << "Parentblk " << *bbParent << "\n";
            //errs() << "userblk " << *user_block << "\n";
            /* post dominator */

            // errs() << "even beyond\n";

            bool not_all_parents_dominated_by_icmp_block = false;


            // errs() << "replaced inst is " << *replacedInst << "\n";

            // errs() << "user insr is " << *user_inst << "\n";
            // errs() << "user_block is " << *user_block << "\n";


            for (pred_iterator PI1 = pred_begin(user_block), E1 = pred_end(user_block); PI1 != E1; ++PI1)
            {
              BasicBlock *Pred = *PI1;
              if(!DT.properlyDominates(bbParent, Pred))
              {
                not_all_parents_dominated_by_icmp_block = true;
              }
            }



            bool phi_present = false;
            for(BasicBlock::iterator b_it = user_block->begin(); b_it != user_block->end(); b_it++)
            {
              Instruction *binst = &*b_it;
              // PHINode *bpinst = dyn_cast<PHINode>(binst);
              if(binst->getOpcode() == Instruction::PHI)
              {
                PHINode *bpinst = dyn_cast<PHINode>(binst);
                //  if(bpinst->getNumIncomingValues() > 1)
                // {  
                phi_present = true;
                for(std::vector<BasicBlock *>::iterator par_it = dominated_parents.begin(); par_it != dominated_parents.end(); par_it++)
                {
                  BasicBlock *Parent = *par_it;
                  int index = bpinst->getBasicBlockIndex(Parent);
                  if (index == -1)
                  {
                    bpinst->addIncoming(replacingInst, Parent);
                    //errs() << *Parent << "\n";
                    //errs() << *bpinst << "\n";
                  }
                  if(replacedInst == bpinst->getIncomingValueForBlock(Parent))
                  {
                    bpinst->setIncomingValue(index, replacingInst);
                  }
                }
                // }
              }

            }
            if(CreatePHI && !phi_present && !not_all_parents_dominated_by_icmp_block)
            {
              int num_of_parent_blocks = 0;
              for (pred_iterator PI1 = pred_begin(user_block), E1 = pred_end(user_block); PI1 != E1 ; ++PI1)                                                                  
                num_of_parent_blocks++;

              IRBuilder<> *builder = new IRBuilder<>(user_block);
              BasicBlock::iterator insertPointInSuccBlk = user_block->begin();
              builder->SetInsertPoint(user_block, *insertPointInSuccBlk);
              //errs() << "current basicblock " << *user_block << "\n";
              
              phi_created = true;

              PHINode *Pi = builder->CreatePHI(replacingInst->getType(), "newPi");

              //Pi->reserveOperandSpace(Pi->getNumIncomingValues());
              for(std::vector<BasicBlock *>::iterator par_it = dominated_parents.begin(); par_it != dominated_parents.end(); par_it++)
              {
                BasicBlock *Parent = *par_it;
                Pi->addIncoming(replacingInst, Parent);
              }

              std::pair<BasicBlock*, BasicBlock*> new_sibling_blocks;
              new_sibling_blocks.first = ((Instruction *)replacedInst)->getParent();
              new_sibling_blocks.second = ((Instruction *)Pi)->getParent();

              /* Propagate the name corresponding to the newly generated PHI */
              replace(replacedInst, Pi, DT, DF, true, new_sibling_blocks);

            }
          }
          else
          { // DOES NOT POST DOMINATE

            // errs() << "else\n";

            bool phi_present = false;
            for(BasicBlock::iterator b_it = user_block->begin(); b_it != user_block->end(); b_it++)
            {
              Instruction *binst = &*b_it;
              if(binst->getOpcode() == Instruction::PHI)
              {
                PHINode *bpinst = dyn_cast<PHINode>(binst);
                phi_present = true;
                //errs() << "phi present " << *binst << "\n"; 
                for(std::vector<BasicBlock *>::iterator par_it = dominated_parents.begin(); par_it != dominated_parents.end(); par_it++)
                {

                  BasicBlock *Parent = *par_it;
                  if(replacedInst == bpinst->getIncomingValueForBlock(Parent))
                  {
                    int index = bpinst->getBasicBlockIndex(Parent);
                    if (index == -1)
                    {
                      bpinst->addIncoming(replacingInst, Parent);
                    }
                    if(replacedInst == bpinst->getIncomingValueForBlock(Parent))
                    {
                      bpinst->setIncomingValue(index, replacingInst);
                    }
                  }
                }
              }
            }
          }
        }
      }
    }

 /*  if(CreatePHI)
    {
      std::map<Instruction *, std::list<Instruction *> >::iterator replacement_pair_if_any = lookup_for_other_branch.find((Instruction *)replacedInst);
      if(replacement_pair_if_any != lookup_for_other_branch.end())
      {
        std::list<Instruction *> obl = (*replacement_pair_if_any).second;

        for(std::list<Instruction *>::iterator oit = obl.begin(); oit!= obl.end(); oit++)
        {
         Instruction *other_branch_inst = *oit;
         fillinjoinphi(other_branch_inst, replacingInst, DT, PDT);
        }
      }
      else
      {
       std::pair<Instruction *, std::list <Instruction *> > replacement_pair;
       replacement_pair.first = (Instruction *)replacedInst;
       std::list<Instruction *> *list = new std::list<Instruction *>();
       replacement_pair.second = *list;
       replacement_pair.second.push_back(replacingInst);

       lookup_for_other_branch.insert(lookup_for_other_branch.begin(), replacement_pair);
      }
    }*/
    return phi_created;
  }

  void eSSAPass2::fillinjoinphi(Instruction *other_branch_inst, Instruction *replacingInst, DominatorTree &DT, DominanceFrontier &DF, std::pair<BasicBlock*, BasicBlock*> sibling_blocks)
  {
  //  errs() << "coming to replace PHI " << *replacingInst << "  " << *other_branch_inst << "\n";

    std::list <Instruction *> u_list;
    BasicBlock *bbParent=replacingInst->getParent()->getUniquePredecessor();
    if (bbParent == NULL)
      return;
    for(Value::use_iterator u_it_l = other_branch_inst->use_begin(); u_it_l != other_branch_inst->use_end(); u_it_l++)
    {
      Instruction * user_inst = (Instruction *)((u_it_l.getUse()).getUser());
      u_list.push_back(user_inst);
    }

    for (std::list <Instruction *>::iterator inst_it = u_list.begin(); inst_it != u_list.end(); inst_it++)
    {
      Instruction * user_inst = *inst_it;
      BasicBlock *user_block = user_inst->getParent();
      BasicBlock *defining_block = replacingInst->getParent();
      if(!DT.properlyDominates(defining_block, user_block))  
      {
        bool dominates_parent = false;
        std::vector <BasicBlock *> dominated_parents;
        for (pred_iterator PI = pred_begin(user_block), E = pred_end(user_block); PI != E; ++PI) 
        {
          BasicBlock *Pred = *PI;
          if(DT.dominates(defining_block, Pred))
          {
            dominates_parent = true;
            dominated_parents.push_back(Pred);
          }

        } 

        if(dominates_parent)
        {
          /* is a dominance frontier */

          BasicBlock* sibBlock = sibling_blocks.first;
          if (replacingInst->getParent() == sibBlock)
            sibBlock = sibling_blocks.second;

          if (isInDomFrontier(DT, user_block, sibBlock))
          {
           // for(BasicBlock::iterator b_it = user_block->begin(); b_it != user_block->end(); b_it++)
           // {
             // Instruction *binst = &*b_it;

              if(user_inst->getOpcode() == Instruction::PHI)
              {
                PHINode *bpinst = dyn_cast<PHINode>(user_inst);
                for(std::vector<BasicBlock *>::iterator par_it = dominated_parents.begin(); par_it != dominated_parents.end(); par_it++)
                {
                  //errs() << "almost inserting \n";
                  BasicBlock *Parent = *par_it;
                  int index = bpinst->getBasicBlockIndex(Parent);
                  if (index == -1)
                    bpinst->addIncoming(replacingInst, Parent);
                }

                for (int i = 0; i < bpinst->getNumIncomingValues(); i++)
                {
                  Value *v = bpinst->getIncomingValue(i);
                  std::pair<BasicBlock*, BasicBlock*> new_sibling_blocks;
                  new_sibling_blocks.first = ((Instruction *)v)->getParent();
                  new_sibling_blocks.second = ((Instruction *)bpinst)->getParent();
                  replace(v, bpinst, DT, DF, true, new_sibling_blocks);
                }
              }
           // }
          }
        }
      }
    }
    return;
  }

  char eSSAPass2::ID = 0;
  static RegisterPass<eSSAPass2> Y("eSSAPass2", "Extending SSA to eSSA in ABCD algorithm2", false, false);
}
